Ćwiczenia/2. Ćwiczenia/Zadanie 6. (największy przedział).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dany jest ciąg przedziałów domkniętych [a1, b1], . . . , [an, bn]. Proszę zapropnować algorytm, który znajduje taki przedział [at, bt], w którym w całości zawiera się jak najwięcej innych przedziałów."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naszym celem jest znalezienie takiego przedziału, który będzie zawierał w sobie najwięcej przedziałów. Najłatwiej jest to osiągnąć, przygotowując sobie uprzednio listę (Pythonową - aka tablica) z przedziałami, sortując ją według początku przedziału, a jeżeli istnieje kilka (przynajmniej 2) przedziałów, które zaczynają się w tym samym miejscu, również według tego, który kończy się później (tzn. najpierw będą te dłuższe, zakończone później - tylko, jeżeli zaczynają się w tym samym miejscu). Przyjmujemy taką taktykę ponieważ można łatwo zauważyć, że idąc od lewej strony (zaczynając od przedziałów, które zaczynają najmniejszą wartością), kolejno będziemy odwiedzać tylko takie przedziały, które mają szansę w całości się znaleźć w obecnie wizytowanym przedziale. (tzn. bez sensu jest sprawdzać te, które zaczynają się wcześniej, bo z tego powodu wiemy, że nie mogą one znaleźć się w całości wewnątrz obecnie rozpatrywanego przedziału)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}